class Solution(object):
    def find132pattern(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        a_stack = []
        last_stack = [nums[0]]
        n = len(nums)
        for i in range(1, n):
            if nums[i] < last_stack[-1]:
                if len(last_stack) == 2:
                    if nums[i] > last_stack[0]:
                        return True
                    else:
                        if nums[i] < last_stack[0]:
                            a_stack.append([last_stack[0], last_stack[1]])
                            last_stack = [nums[i]]
                else:
                    last_stack = [nums[i]]
            else:
                if nums[i] > last_stack[-1]:
                    if a_stack:
                        if nums[i] >= a_stack[0][1]:
                            a_stack = []
                        else:
                            t = len(a_stack)
                            k = t - 1
                            while k >= 0:
                                if nums[i] < a_stack[k][1]:
                                    if nums[i] > a_stack[k][0]:
                                        return True
                                    else:
                                        break
                                else:
                                    k -= 1
                            a_stack = a_stack[:k + 1]
                    if len(last_stack) == 1:
                        last_stack.append(nums[i])
                    else:
                        last_stack[-1] = nums[i]
        return False


data = Solution()
nums = [3, 1, 4, 2]
print(data.find132pattern(nums))
nums = [100, 200, 50, 90, 10, 40, 101]
print(data.find132pattern(nums))